//题目:
// 在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。
#include<iostream>
#include<math.h>
#include<vector>

using namespace std;
//代码
class Solution 
{
public:
    int maximalSquare(vector<vector<char>>& matrix) 
    {
        int m=matrix.size(),n=matrix[0].size();
        //1.创建dp表————dp[i][j]表示：以(i,j)位置为右下角的正方形的最大面积
        vector<vector<int>> dp(m+1,vector<int>(n+1));
        //2.初始化————暂无
        //3.填表————动态转移方程:dp[i][j]=(min(dp[i-1][j],dp[i][j-1])开根号+1)^2
        int ret=0;
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(matrix[i-1][j-1]=='1')
                {
                    dp[i][j]=1;
                    int len=sqrt(min(dp[i-1][j],dp[i][j-1]));
                    if(dp[i-1][j-1]!=0)
                    {
                        
                        if(dp[i-len][j-len]!=0)
                            dp[i][j]=pow(len+1,2); 
                        else
                            dp[i][j]=pow(len,2);                                            
                    }
                }
                ret=max(ret,dp[i][j]);
            }
        }
        //4.确定返回值
        return ret;
    }
};